package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/daily-temperatures/">每日温度(Daily Temperatures)</a>
 * <p>给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: temperatures = [73,74,75,71,69,72,76,73]
 *      输出: [1,1,4,2,1,1,0,0]
 *
 * 示例 2:
 *      输入: temperatures = [30,40,50,60]
 *      输出: [1,1,1,0]
 *
 * 示例 3:
 *      输入: temperatures = [30,60,90]
 *      输出: [1,1,0]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= temperatures.length <= 10^5</li>
 *     <li>30 <= temperatures[i] <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/4 14:54
 */
public class LC0739DailyTemperatures_M {

    static class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            // 从左到右遍历温度数组。使用单调递减的栈来保存每日温度的idx
            int[] res = new int[temperatures.length];
            Deque<Integer> idxStack = new LinkedList<>();
            for (int idx = 0; idx < temperatures.length; idx++) {
                // 如果当前温度，大于历史温度，清算历史温度
                while (!idxStack.isEmpty() && temperatures[idx] > temperatures[idxStack.peekFirst()]) {
                    int sourceIdx = idxStack.removeFirst();
                    res[sourceIdx] = idx - sourceIdx;
                }
                // 如果当前温度，小于等于历史温度，将对应下标加到栈中，等待被未来温度清算。
                idxStack.addFirst(idx);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}));
        Printer.printArrayInt(solution.dailyTemperatures(new int[]{30, 40, 50, 60}));
        Printer.printArrayInt(solution.dailyTemperatures(new int[]{30, 60, 90}));
    }
}